Đội bóng đá Tổng cục Đường sắt được thành lập vào năm 1956, là một trong những đội bóng được thành lập đầu tiên của miền Bắc nói chung và của Hà Nội nói riêng. Trong suốt thời gian chiến tranh, đội lừng danh, chỉ xếp sau đội Thể Công về thành tích và mức độ hâm mộ của khán giả.

Ngày 7 tháng 11 năm 1976, đội với tư cách là đội bóng hàng đầu đại diện cho miền Bắc Việt Nam, đã có trận thi đấu lịch sử với đội bóng hàng đầu đại diện cho miền Nam Việt Nam bấy giờ là Cảng Sài Gòn[1].

Năm 1980, đội trở thành đội bóng đầu tiên đoạt chức vô địch Giải bóng đá vô địch toàn quốc lần thứ nhất. Trong giải này, đội bóng mạnh nhất Việt Nam bấy giờ là Thể Công xin rút không thi đấu.

Tại mùa bóng 1985, đội thi đấu không thành công, xếp cuối cùng trong vòng chung kết ngược, phải xuống thi đấu ở hạng A2.

Năm 1989, Tổng cục Đường sắt giải thể, chuyển thành một Doanh nghiệp Nhà nước với tên là Liên hiệp Đường sắt Việt Nam, hoạt động trên nguyên tắc thị trường mở. Đội bóng cũng được đổi tên thành Đội bóng đá Đường sắt Việt Nam, tuy nhiên các khán giả vẫn quen gọi là đội bóng Tổng cục Đường sắt.